package me.qingy.programmatic;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 反转两次，以及 trim() reverse() 函数实现练习
 *
 * @author qingy
 * @since 2021/8/18
 */
public class ReverseWords {

    /**
     * 反转两次
     */
    public String reverseWords(String s) {
        char[] chars = s.toCharArray(); // 转换输入格式，并不算核心逻辑，不算入复杂度计算

        int n = trim(chars);
        if (n == 0) return "";
        reverse(chars, 0, n - 1);

        int p = 0;
        while (p < n) {
            int r = p; // 通过 r 记录单词长度，调用翻转方法
            while (r < n && chars[r] != ' ') {
                r++;
            }
            reverse(chars, p, r - 1);
            p = r + 1;
        }

        // 转换输出格式，并不算核心逻辑，不算入复杂度计算
        char[] result = Arrays.copyOf(chars, n);
        System.arraycopy(chars, 0, result, 0, n);
        return new String(result);
    }

    /**
     * 原地删除前置空格、后置空格、多余空格，返回新长度
     */
    public int trim(char[] chars) {
        int n = chars.length;
        int i = 0;
        int k = 0; // 去除多余空格后的长度

        // 前置空格
        while (i < n && chars[i] == ' ') {
            i++;
        }
        while (i < n) {
            if (chars[i] != ' ') {
                chars[k++] = chars[i];
            } else {
                // 多余空格、后置空格
                if (i + 1 < n && chars[i + 1] != ' ') {
                    chars[k++] = ' ';
                }
            }
            i++;
        }

        return k;
    }

    /**
     * 反转 start 与 end 之间的字符
     */
    public void reverse(char[] chars, int start, int end) {
        // [0,1,2,3,4,5] start 2 end = 4 mid = 3
        int mid = (start + end) / 2;
        for (int i = start; i <= mid; i++) { // <= mid 否则偶数长度的数组不翻转
            char tmp = chars[i];
            // end - (i - start) => chars[i] 的镜像位置
            chars[i] = chars[end - (i - start)];
            chars[end - (i - start)] = tmp;
        }
    }

    public String reverseWordsSplit(String s) {
        // trim() 函数并不是为这种实现方式而写的，勉强拉进来用用
        char[] chars = s.toCharArray();
        char[] newChars = Arrays.copyOf(chars, trim(chars));

        s = new String(newChars);
        String[] array = s.split(" "); // 空间复杂度 O(n)
        int n = array.length;

        for (int i = 0; i < n / 2; i++) {
            String tmp = array[i];
            array[i] = array[n - 1 - i];
            array[n - 1 - i] = tmp;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(array[i]);
            if (i < n - 1) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }

    @Test
    public void testReverseWords() {
        Assertions.assertEquals("blue is sky the", reverseWords("the sky is blue"));
        Assertions.assertEquals("world! hello", reverseWords("  hello world!  "));
        Assertions.assertEquals("example good a", reverseWords("a good   example"));

        Assertions.assertEquals("  hello    world!  ".length() - 7, trim("  hello world!  ".toCharArray()));

        char[] c1 = new char[]{'h', 'e', 'l', 'l', 'o'};
        reverse(c1, 1, 3);
        char[] c2 = new char[]{'i', 's'};
        reverse(c2, 0, 1);
        Assertions.assertArrayEquals(new char[]{'h', 'l', 'l', 'e', 'o'}, c1);
        Assertions.assertArrayEquals(new char[]{'s', 'i'}, c2);
    }
}
